//给定一个未排序的整数数组，找出最长连续序列的长度。 
//
// 要求算法的时间复杂度为 O(n)。 
//
// 示例: 
//
// 输入: [100, 4, 200, 1, 3, 2]
//输出: 4
//解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。 
// Related Topics 并查集 数组 
// 👍 477 👎 0

package leetcode.editor.cn;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

//Java：最长连续序列
public class P128LongestConsecutiveSequence {
    public static void main(String[] args) {
        Solution solution = new P128LongestConsecutiveSequence().new Solution();
        // TO TEST
        int input[]={9,1,4,7,3,-1,0,5,8,-1,6};
    int res=solution.longestConsecutive2(input);
        System.out.println(res);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /*
         *  尝试使用动态规划来解决这个问题
         *  遇到 1 2 0 1无法通过
         * */
        public int longestConsecutive1(int[] nums) {
            if(nums==null||nums.length<=0){
                return 0;
            }
            int len=nums.length;

            Arrays.sort(nums);
            int[] dp=new int[len];
            for(int i=0;i<len;i++){
                dp[i]=1;
            }
            int max=1;
            for(int i=1;i<len;i++){
                if (nums[i]-1==nums[i-1]){
                    dp[i]=dp[i-1]+1;
                    max=max>dp[i]?max:dp[i];
                }
            }
            return max;
        }

        /*
        * 使用一个set
        * 时间复杂度为O(n^2)
        * */
        public int longestConsecutive2(int[] nums) {
            if(nums==null||nums.length<=0){
                return 0;
            }

            Set<Integer> set=new HashSet<>();
            for(int e:nums){
                set.add(e);
            }

            int max=1;

            for(int i=0;i<nums.length;i++){
                int left=0,right=0;
                int a=nums[i]+1,b=nums[i]-1;
                while(set.contains(a++)){
                    right++;
                }
                while (set.contains(b--)){
                    left--;
                }
                max=max>(right-left+1)?max:(right-left+1);
            }

            return max;
        }


        /*
         * 使用一个set
         * 尝试优化
         * （1）会存在很多的重复计算
         * 如 100 4 200 1 3 2
         * 对于4  计算出来结果为 4 1 3 2
         * 对于1  计算出来结果同样为 4 1 3 2
         * ...
         *
         * 优化  只用找最小的  单向增长即可
         * 这种解法的时间复杂度为O(n)的时间复杂度，因为只有找到最小的时候才会进行while循环，以上重复计算不再存在
         * */
        public int longestConsecutive3(int[] nums) {
            if(nums==null||nums.length<=0){
                return 0;
            }

            Set<Integer> set=new HashSet<>();
            for(int e:nums){
                set.add(e);
            }

            int max=0;

            for(int i=0;i<nums.length;i++){
                int num=nums[i];
                if(!set.contains(num-1)){//不包含比它小的数
                    int count=0;
                    while(set.contains(num)){
                        count++;
                        num+=1;
                    }
                    max=Math.max(max,count);
                }
            }

            return max;
        }

        /*
        * 使用HashMap
        * 回到刚才使用set的时候，使用while循环计算左边的值和右边的值出现重复计算的问题，我们可以使用一个HashMap保存一个数字左边的长度和右边的长度。
        * 一个数字连续的长度等于比它小一个数的左边的长度和比它大一个数的右边的长度
        *
        * */

        public int longestConsecutive(int[] nums) {
            if(nums==null||nums.length<=0){
                return 0;
            }

            //用hash表存储每个端点值对应连续区间的长度
            HashMap<Integer,Integer> map=new HashMap<>();
            int max=0;

            for(int num:nums){
                //若数已在哈希表中，跳过不做处理
                if(!map.containsKey(num)){
                    //如果是新数   100 4 200 1 3 2
                    int left=map.get(num-1)==null?0:map.get(num-1);
                    int right=map.get(num+1)==null?0:map.get(num+1);
                    int cur=1+left+right;
                    max=max>cur?max:cur;

                    map.put(num,cur);
                    map.put(num-left,cur);
                    map.put(num+right,cur);
                }
            }

            return max;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
